package leetcode.code2467;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	Map<Integer, Integer> bobs;
	int ans;
	int[] amount;
	List<Integer>[] nexts;

	public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
		this.amount = amount;
		int len = edges.length;
		int n = len + 1;
		nexts = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < len; i++) {
			int[] e = edges[i];
			int a = e[0], b = e[1];
			nexts[a].add(b);
			nexts[b].add(a);
		}
		bobs = new HashMap<>();
		ans = Integer.MIN_VALUE;
		findBob(-1, 0, bob);
		tryAlice(-1, 0, 0, 0);
		return ans;
	}

	private void tryAlice(int from, int time, int start, int point) {
		List<Integer> next = nexts[start];
		int bob = bobs.getOrDefault(start, -1);
		int amt = this.amount[start];
		if (bob != -1) {
			if (bob == time) {
				amt >>= 1;
			} else if (bob < time) {
				amt = 0;
			}
		}
		point += amt;
		if (next.size() == 1 && from != -1) {
			ans = Math.max(ans, point);
			return;
		}
		for (int n : next) {
			if (n != from) {
				tryAlice(start, time + 1, n, point);
			}
		}
	}

	private int findBob(int from, int start, int bob) {
		if (start == bob) {
			bobs.put(bob, 0);
			return 1;
		}
		List<Integer> next = nexts[start];
		if (next.size() == 1 && from != -1) {
			return -1;
		}
		for (int n : next) {
			if (n != from) {
				int cur = findBob(start, n, bob);
				if (cur != -1) {
					bobs.put(start, cur);
					return cur + 1;
				}
			}
		}
		return -1;
	}

	@Override
	public void debug4() {
		H.compare(6,
				this.mostProfitablePath(H.str2array1("[[0,1],[1,2],[1,3],[3,4]]"), 3, H.str2array3("[-2,4,2,-4,6]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
